归并排序 --分治初探

先上代码：

public class MergeSort {					//差不多照书敲得
    private  int[] myarray = new int[10];
    public int[] getMyarray() {
        return myarray2;
    }
    private  int [] myarray2;
    public MergeSort() {
    }
    public void  MergeSort(int array[], int start, int end) {
        int mid;
        if (start == end)
            return;
        else {
            mid = (start + end) / 2;
            MergeSort(array, start, mid);
            MergeSort(array, mid + 1, end);
            Merge(array, myarray,start,mid,end);
            for (int i = start; i <= end; i++) {
               array[i]= myarray[i];
            }
        }
        myarray2 = array;
    }


    void Merge(int array[], int r1[], int start, int mid, int end)//归并
    {
        int first = start, second =mid+1, k =start ;
	    while (first<=mid && second <=end)          
        {
            if (array[first]<= array[second])
                r1[k++] = array[first++];
            else
                r1[k++] = array[second++];
        }
        while (first<=mid)
        {
            r1[k++]= array[first++];
        }
        while (second<=end)
        {
            r1[k++]= array[second++];
        }
    }
}

来个维基百科的图片

我们可以看出要先将大数组分为两个小数组，小数组继续分，直到分为只有一个数，不可再分；简单来说我们要对每一个成员进行去排序；

那么排序实际在哪里发生呢？归并的时候嘛，所以叫做归并排序；
如果是递归的话，你可以看到的是什么呢？





上面是关于归并具体的情况，我们可以清楚的看到程序先做了小型的排序，最后做了最大的排序；和我们的想法一模一样；

简单地说 归并排序有两个操作
1.将数组分解；
2.对两个数组进行归并排序